package _动态规划系列._套路框架;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/30 11:41
 * <p>
 * 功能描述:    凑零钱问题
 */
public class Summary_0322 {

    public static void main(String[] args) {
        Summary_0322 test = new Summary_0322();
        int[] coins = {1, 2, 5};
        int amount = 11;
        test.coinChange1(coins, amount);
    }

    /*----------------------------------------自底向上的dp-----------------------------------*/

    /**
     * 迭代dp。常用的dp方式就是循环迭代的方式,而不是递归
     * dp[i]: 当金额为i时，凑齐i的最少硬币数量
     */
    public int coinChange1(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);

        //base case
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin < 0)
                    continue;
                //做选择，选择硬币。如果选了当前硬币那么就要+1，然后再算dp[i - 你选的那个硬币]
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }

        return dp[amount] == (amount + 1) ? -1 : dp[amount];
    }

    /*--------------------------------------------------------------------------------------*/



    /*----------------------------------------自顶向下的dp------------------------------------*/
    /**
     * 自顶向下的dp,也就是递归式的dp
     * <p>
     * 输入: coins = [1, 2, 5], amount = 11
     * 输出: 3
     * 解释: 11 = 5 + 5 + 1
     */

    int[] myCoins;
    Map<Integer, Integer> memo = new HashMap();

    public int coinChange(int[] coins, int amount) {
        myCoins = coins;

        return dpHelper(amount);
    }

    public int dpHelper(int amount) {

        if (memo.containsKey(amount))
            return memo.get(amount);

        if (amount == 0)
            return 0;
        if (amount < 0)
            return -1;

        int res = Integer.MAX_VALUE;
        for (int coin : myCoins) {
            int subProblem = dpHelper(amount - coin);
            if (subProblem < 0)
                continue;
            res = Math.min(res, 1 + subProblem);
        }
        int val = res == Integer.MAX_VALUE ? -1 : res;
        memo.put(amount, val);

        return memo.get(amount);
    }


    /*--------------------------------------------------------------------------------------*/
}
